package sword_to_1;

import java.util.Stack;

public class LeeCode_31 {
    public static void main(String[] args) {
        System.out.println(validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 2, 1}));
    }
    private static boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        while (i < pushed.length){
            if (stack.isEmpty()){
                stack.push(pushed[i++]);
            }else {
                if (stack.peek() == popped[j]){
                    stack.pop();
                    j++;
                }else {
                    stack.push(pushed[i++]);
                }
            }
        }
        while (!stack.isEmpty()){
            if (stack.pop() != popped[j++]){
                return false;
            }
        }
        return j == popped.length;
    }
}
